#include <iostream>
#include <vector>
#include <queue>
#include <random>
using namespace std;

// val may be other type, here use int for demonstration only, we could use template indeed.

struct TreeNode {
    int _val;
    int _height;
    TreeNode *_left;
    TreeNode *_right;
    TreeNode(int val, int height=0, TreeNode *left=nullptr, TreeNode *rght=nullptr)
        : _val(val), _height(height), _left(left), _right(nullptr) {}
};

class AVLTree {
public:
    AVLTree() : _total_elem(0), _root(nullptr) {}
    ~AVLTree() {
        Clear();
    }
    TreeNode*  FindMin() {
        if (_root == nullptr) return _root;
        TreeNode *min = _root;
        while (min->_left != nullptr) min = min->_left;
        return min;
    }
    TreeNode* FindMax() {
        if (_root == nullptr) return _root;
        TreeNode *max = _root;
        while (max->_right != nullptr) max = max->_right;
        return max;
    }
    TreeNode* Find(int val) {
        TreeNode *n = _root;
        while (n != nullptr && n->_val != val) {
            if (n->_val < val) n = n->_right;
            else n = n->_left;
        }
        return n;
    }
    void Insert(int val) {
        _root = Insert(val, _root);
    }
    void Clear() {
        queue<TreeNode*> q;
        if (_root != nullptr) q.push(_root);
        while (!q.empty()) {
            TreeNode *n = q.front();
            q.pop();
            if (n->_left != nullptr) q.push(n->_left);
            if (n->_right != nullptr) q.push(n->_right);
            delete n;
        }
        _root = nullptr;
    }
    void InorderTraverse(vector<int> &r) {
        if (_root != nullptr) {
            cout << "Total Tree Elem: " << _total_elem << endl;
            cout << "Tree Height: " << _root->_height << endl;
        }
        InorderTraverse(r, _root);
    }

private:
    int _total_elem;
    TreeNode *_root;
    int Height(TreeNode *n) {
        if (n == nullptr) {
            return -1;
        }
        else {
            return n->_height;
        }
    }
    TreeNode* Insert(int val, TreeNode *n) {
        if (n == nullptr) {
            n = new TreeNode(val);
            ++_total_elem;
            return n;
        } 
        if (val < n->_val) {
            n->_left = Insert(val, n->_left);
            if ((Height(n->_left) - Height(n->_right)) >= 2) {
                if (val < n->_left->_val)
                    n = SingleRotateWithLeft(n);
                else
                    n = DoubleRotateWithLeft(n);
            }
        }
        else if (val > n->_val) {
            n->_right = Insert(val, n->_right);
            if ((Height(n->_right) - Height(n->_left)) >= 2) {
                if (val < n->_right->_val)
                    n = DoubleRotateWithRight(n);
                else
                    n = SingleRotateWithRight(n);
            }
        } // else ignore equal case
        n->_height = max(Height(n->_left), Height(n->_right)) + 1;
        return n;
    }
    TreeNode* SingleRotateWithLeft(TreeNode *n) {
        TreeNode *m = n->_left;
        n->_left = m->_right;
        m->_right = n;
        n->_height = max(Height(n->_left), Height(n->_right)) + 1;
        m->_height = max(Height(m->_left), Height(m->_right)) + 1;
        return m;
    }
    TreeNode* SingleRotateWithRight(TreeNode *n) {
        TreeNode *m = n->_right;
        n->_right = m->_left;
        m->_left = n;
        n->_height = max(Height(n->_left), Height(n->_right)) + 1;
        m->_height = max(Height(m->_left), Height(m->_right)) + 1;
        return m;
    }
    TreeNode* DoubleRotateWithLeft(TreeNode *n) {
        n->_left = SingleRotateWithRight(n->_left);
        return SingleRotateWithLeft(n);
    }
    TreeNode* DoubleRotateWithRight(TreeNode *n) {
        n->_right = SingleRotateWithLeft(n->_right);
        return SingleRotateWithRight(n);
    }
    void InorderTraverse(vector<int> &r, TreeNode *n) {
        if (n == nullptr) return;
        if (n->_left != nullptr) InorderTraverse(r, n->_left);
        r.push_back(n->_val);
        if (n->_right != nullptr) InorderTraverse(r, n->_right);
    }
};

int main()
{
    mt19937 rng;
    rng.seed(random_device()());
    uniform_int_distribution<mt19937::result_type> dist(1, 1000000);
    AVLTree t;
    for (int i = 0; i < 10000; ++i) {
        t.Insert(dist(rng));
    }
    vector<int> r;
    t.InorderTraverse(r);
    for (size_t i = 0; i < r.size(); ++i) {
        for (size_t j = i + 1; j < r.size(); ++j) {
            if (r[j] < r[i]) {
                cout << "AVLTree fail!" << endl;
                return -1;
            }
        }
    }
    cout << "AVLTree success!" << endl;
    return 0;
}


